import java.io.FileInputStream;
import java.io.IOException;

public class BTree {
	public class Node {
		public char m_base;
		public Node lt;
		public Node rt;
	}

	private Node root;
	
	public Node getRoot()
	{
		return root;
	}
	
	public BTree(FileInputStream in) throws IOException{
		readTree(in, root);
	}
	
	private Node combine(char x, Node lst, Node rst){
		Node p = new Node();
		p.m_base = x;
		p.lt = lst;
		p.rt = rst;
		
		root = p;
		
		return p;
	}
	
	private Node readTree(FileInputStream in, Node tree) throws IOException
	{
		Node left = null;
		Node right = null;
		char base, sec;
		base = (char) in.read();
		if(base == '(')
		{
			tree = readTree(in, tree);
			return tree;
		}
		//System.out.println("Base: " + base);

		
		sec = (char) in.read();
		if(sec== ')')
		{
			sec = (char) in.read();
		}

		if(sec == '(')
		{
			left = readTree(in, left);
		}
		//System.out.println("Sec1: " + sec);


		sec = (char) in.read();
		if(sec== ')')
		{
			sec = (char) in.read();
		}
		//System.out.println("Sec2: " + sec);

		if(sec == '(')
		{
			right = readTree(in, right);
		}
		
		tree = combine(base, left, right);
		return tree;
	}
	
	public void display()
	{
		display(root, 0);
	}
	
	private void display (Node b, int n)
	{	
		if (b != null) {
			System.out.print(" " + b.m_base); 
			if(b.rt != null) {
				for (int i=1;i<=n;i++) 
				{
					System.out.print(" ");
				}
				display (b.rt,n+1);
			}
			else System.out.print("\n");
			if(b.lt != null) {
				for (int i=1;i<=n;i++) 
				{
					System.out.print(" ");
				}
				display (b.lt,n+1);
			}
		}
	}
	
	public boolean isSimilar(BTree tree)
	{
		return isSimilar(this.getRoot(), tree.getRoot());
	}
	private boolean isSimilar(Node node1, Node node2)
	{
		if(node1 == null && node2 == null){
			return true;
		}
		else if (node1 == null || node2 == null){
			return false;

		}

		boolean left_left = isSimilar(node1.lt, node2.lt);
		boolean right_right = isSimilar(node1.rt, node2.rt);

		return left_left && right_right;
	}


	public boolean isEqual(BTree tree)
	{
		return isEqual(this.getRoot(), tree.getRoot());
	}
	private boolean isEqual(Node node1, Node node2)
	{
		if(node1 == null && node2 == null){
			return true;
		}
		else if (node1 == null || node2 == null){
				return false;
		}
	
		boolean equalBase = (node1.m_base == node2.m_base);
	
		boolean left_left = isEqual(node1.lt, node2.lt);
		boolean right_right = isEqual(node1.rt, node2.rt);
	
		return equalBase && left_left && right_right;
	}
	
	public boolean isMirrorSimilar(BTree tree)
	{
		return isMirrorSimilar(this.getRoot(), tree.getRoot());
	}
	private boolean isMirrorSimilar(Node node1, Node node2)
	{
		if(node1 == null && node2 == null){
			return true;
		}
		else if (node1 == null || node2 == null){
			return false;
		}
	
		boolean left_right = isMirrorSimilar(node1.lt, node2.rt);
		boolean right_left = isMirrorSimilar(node1.rt, node2.lt);
	//	cout << "Left - Right: " << left_right << " Right - Left: " << right_left << endl;
	
		return left_right && right_left;
	}
	
	public boolean isMirrorEqual(BTree tree)
	{
		return isMirrorEqual(this.getRoot(), tree.getRoot());
	}
	private boolean isMirrorEqual(Node node1, Node node2)
	{
		if(node1 == null && node2 == null){
			return true;
		}
		else if (node1 == null || node2 == null){
			return false;
		}
	
		boolean equalBase = (node1.m_base == node2.m_base);
	//	cout << "node1 base: " << node1.m_base
	//			<< " node2 base: " << node2.m_base
	//			<< " Equal : " << equalBase << endl;
	
		boolean left_right = isMirrorEqual(node1.lt, node2.rt);
		boolean right_left = isMirrorEqual(node1.rt, node2.lt);
	//	cout << "Left - Right: " << left_right << " Right - Left: " << right_left << endl;
	
		return equalBase && left_right && right_left;
	}
}